#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL MOD=998244353;
LL gcd(LL a, LL b) {
	return a%b==0? b : gcd(b, a%b); 
}
int main() {
	#ifdef hai
	freopen("in.txt", "r", stdin);
	#endif
	LL T, ask;
	cin>>T;
	while (T--) {
		cin>>ask;
		LL res=0;
		for (LL i=1; i<=ask; ++i) {
			if (gcd(i, ask)==1) {
				LL ti=i%MOD;
				res=(res+ti*ti%MOD)%MOD;
			}
		}
		cout<<res<<endl;
	}
	return 0;
} 
